package com.heap;

import java.util.Arrays;
import java.util.Comparator;

/**
 * @author `RKC`
 * @date 2021/11/5 9:44
 */
@SuppressWarnings("unchecked")
class PriorityQueue<E> {

    private static final int DEFAULT_INITIAL_CAPACITY = 11;
    private Comparator<E> comparator;
    private Object[] queue;
    private int capacity;
    private int size;

    public PriorityQueue(Comparator<E> comparator) {
        this.comparator = comparator;
        this.queue = new Object[DEFAULT_INITIAL_CAPACITY + 1];
        this.capacity = DEFAULT_INITIAL_CAPACITY;
        size = 0;
        //便于管理，数组的0位置不会使用，置空
        queue[0] = null;
    }

    public void add(Object ele) {
        if (size + 1 > capacity) {
            //容量不够，自动扩容
            grow();
        }
        queue[++size] = ele;
        int index = size;
        int parentIndex = index >> 1;
        //检查是否满足Comparator的条件，以便形成大顶堆/小顶堆。在当前节点检测完之后，移动index指针指向父节点继续检测，直到到达根节点
        while (index > 1 && comparator.compare((E) queue[index], (E) queue[parentIndex]) < 0) {
            Object temp = queue[index];
            queue[index] = queue[parentIndex];
            queue[parentIndex] = temp;
            //移动指针
            index = parentIndex;
            parentIndex = index >> 1;
        }
    }

    public E peek() {
        return (E) queue[1];
    }

    public E poll() {
        if (size < 1) {
            throw new ArrayStoreException("数组中没有元素");
        }
        E removeElement = peek();
        //将最后一个元素赋值给堆顶元素
        queue[1] = queue[size--];
        int index = 1;
        //从堆顶一直往下遍历调整，使其符合堆的特性
        while (index <= (size >> 1)) {
            //完全二叉树性质，右节点不一定存在，但左节点是一定存在的
            int left = index << 1, right = (index << 1) + 1;
            //当前节点的值和孩子进行比较，和右孩子比较时需要要求右孩子在有效范围内
            if ((comparator.compare((E) queue[index], (E) queue[left]) > 0) || (right <= size && comparator.compare((E) queue[index], (E) queue[right]) > 0)) {
                int childIndex = left;
                if (right <= size && comparator.compare((E) queue[left], (E) queue[right]) > 0) {
                    childIndex = right;
                }
                //调整
                Object temp = queue[childIndex];
                queue[childIndex] = queue[index];
                queue[index] = temp;
                index = childIndex;
            } else {
                break;
            }
        }
        return removeElement;
    }

    public int size() {
        return size;
    }

    private void grow() {
        int oldCapacity = queue.length;
        //自动扩容1.5倍
        int newCapacity = oldCapacity + (oldCapacity >> 1);
        queue = Arrays.copyOf(queue, newCapacity);
    }

    public static void main(String[] args) {
        PriorityQueue<Integer> priorityQueue = new PriorityQueue<>((o1, o2) -> o2 - o1);
        for (int i = 1; i <= 20; i++) {
            priorityQueue.add(i);
        }
        System.out.println(priorityQueue);
        for (int i = 1; i <= 5; i++) {
            System.out.println(priorityQueue.poll());
            System.out.println(priorityQueue);
        }
    }

    @Override
    public String toString() {
        if (size == 0) {
            return "No element!";
        } else {
            StringBuilder sb = new StringBuilder();
            sb.append('[');
            for (int i = 1; i <= size; i++) {
                sb.append(queue[i]);
                sb.append(", ");
            }
            sb.deleteCharAt(sb.length() - 1);
            sb.append(']');
            return sb.toString();
        }
    }
}
